package binary_tree.Leetcode;

/**
 * 最近公共祖先——从r出发无论使用哪种遍历方式可以把节点p和q都找到，且p和q一定不在同一颗子树上，则r是p和q的最近公共祖先
 */
public class Num236_LowestCommonAncestor {
    //公共祖先记录
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findNode(root,p,q);
        return lca;
    }
//判断当时树root是否是p或q的祖先
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }
        //用整型变量来记录是否找到节点
        //先在左子树中寻找p或者q
        int left=findNode(root.left,p,q)?1:0;
        //再在右子树中寻找p或q
        int right=findNode(root.right,p,q)?1:0;
        //最后在根节点处寻找p或q
        int mid=(root==p)||(root==q)?1:0;
        if(left+right+mid==2){
            lca=root;
        }
        return (left+right+mid)>0;
    }
}
